Gordov đã chiến đấu trong Chiến tranh Mùa đông với tư cách là tham mưu trưởng Quân đoàn 7, nhưng bị cách chức sau những thất bại được quy kết trách nhiệm liên đới. Ông được chuyển đến làm Tham mưu trưởng Quân khu Baltic. Được thăng cấp Thiếu tướng vào tháng 6 năm 1940, khi Chiến dịch Barbarossa nổ ra, ông được bổ nhiệm làm Tham mưu trưởng Tập đoàn quân 21 và sau đó là Tư lệnh tập đoàn quân này từ tháng 10 năm 1941, chiến đấu trong trận Smolensk và trận Kiev.[4] Tháng 5 năm 1941, Tập đoàn quân 21 tham gia cuộc phản công thảm hại ở Kharkov của Timoshenko, nhưng đã thoát khỏi vòng vây sau đó của Tập đoàn quân 6 của Đức. Cuối tháng 6, Tập đoàn quân 21 tham gia trận chiến Voronezh, với một phần đơn vị bị bao vây bởi Tập đoàn quân thiết giáp số 4 tướng Hermann Hoth.[5] Những gì còn lại của Phương diện quân Tây Nam cũ, bao gồm cả Tập đoàn quân 21 bị thiệt hại, được tái tổ chức lại thành Phương diện quân Stalingrad. Timoshenko được triệu hồi về Moskva, và Gordov được bổ nhiệm làm Tư lệnh Phương diện quân Stalingrad vào ngày 23 tháng 7 năm 1942.[6]